public class Solution169 {
    public int majorityElement(int[] nums) {
        /*
        int count = 0;
        int candidate = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (candidate == num) ? 1 : -1;
        }
        return candidate;*/
        int majorityCount = nums.length / 2;
        while (true) {
            int candidate = nums[(int) (Math.random() * nums.length)];
            int count = 0;
            for (int num : nums) {
                if (num == candidate) {
                    count++;
                }
            }
            if (count > majorityCount) {
                return candidate;
            }
        }
    }
}
